#include <vector>
using namespace std;

vector<long long> preSum;
vector<long long> temp;
int low, up;
int ans = 0;

void mergeSort(vector<long long>& nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    // 统计
    int i = mid+1,j=mid+1;
    for(int k=l;k<=mid;k++){
        while(i <= r && nums[i] - nums[k] < low) i++;
        while(j <= r && nums[j] - nums[k] <= up) j++;
        if(j-i>=0) ans += j-i;
    }
    // 排序
    i = l, j = mid + 1;
    int cur = l;
    while (i <= mid && j <= r) {
        if (nums[j] < nums[i]) {
            temp[cur++] = nums[j++];
        } else {
            temp[cur++] = nums[i++];
        }
    }
    if (i == mid + 1) {
        while (j <= r) temp[cur++] = nums[j++];
    } else {
        while (i <= mid) temp[cur++] = nums[i++];
    }
    for (int t = l; t <= r; t++) nums[t] = temp[t];
}

int countRangeSum(vector<int>& nums, int lower, int upper) {
    preSum.resize(nums.size() + 1);
    temp.resize(nums.size() + 1);
    preSum[0] = 0;
    for (int i = 1; i < preSum.size(); i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; }
    low = lower;
    up = upper;
    mergeSort(preSum, 0, preSum.size() - 1);
    return ans;
}